#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
#include<vector>

using namespace std;

class Solution {
public:
    int random(int left, int right) {
        return rand() % (right - left + 1) + left;
    }
    int partition(vector<int>& nums, int l, int r, int& left, int& right) {
        int key = nums[random(l, r)];
        int cur = l;
        while (cur < right) {
            int n = nums[cur];
            if (n < key) {
                swap(nums[++left], nums[cur++]);
            }
            else if (n == key) {
                cur++;
            }
            else {
                swap(nums[--right], nums[cur]);
            }
        }
        return key;
    }
    int quick_select(vector<int>& nums, int k, int l, int r) {
        if (l == r)
            return nums[l];

        int left = l - 1, right = r + 1;
        int key = partition(nums, l, r, left, right);

        int a = left - l + 1, b = (right - 1) - (left + 1) + 1,
            c = r - right + 1;
        if (c >= k) {
            return quick_select(nums, k, right, r);
        }
        else if (b + c >= k) {
            return key;
        }
        else {
            //(a+b+c>=k)
            return quick_select(nums, k - b - c, l, left);
        }
    }
    int findKthLargest(vector<int>& nums, int k) {
        srand(time(NULL));
        return quick_select(nums, k, 0, nums.size() - 1);
    }
};